package day11;

// 满二叉树找最近的公共结点（也可能是自身）

public class Main1 {

    // 复盘版本：
    // 判断并循环计算父亲结点
    public int getLCA(int a, int b) {
        // write code here

        // 首先进行判断是否相等，也就是循环的条件
        while (a != b) {
            // 序号大的先进行父亲结点的计算
            if(a > b) {
                a /= 2;
            } else {
                b /= 2;
            }
        }

        // 这里说明 a==b，此时已经找到了父亲结点
        return a;
    }



//    // 直接以下就行：使用递归！
//    public int getLCA(int a, int b) {
//        // write code here
//
//        if(a==b){
//            return a;
//        }
//        return ((a>b)?(getLCA(a/2,b)):(getLCA(a,b/2)));
//    }
//
//    public static void main(String[] args) {
//        Main1 main1 = new Main1();
//        int ret = main1.getLCA(16,20);
//        System.out.println(ret);
//    }

    /*// 测试1
    public static int getVal(int i) {  // 传入2
        int ret = 0;
        switch (i) {
            case 1:
                ret = ret + i;
            case 2:
                ret = ret + i*2; // 来到这儿，ret=4
            case 3:
                ret = ret + i*3; // 因为没有break，所以继续向下执行，但是与case无关，只是保持之前的case！！！
                // so：ret = 4 + 2*3 = 6;
        }
        return ret;
    }

    public static void main(String[] args) {
        System.out.println(getVal(2));  //输出结果：10
    }*/



    /*public int getLCA(int a, int b) {
        // write code here

        // 应该是用递归！
        // 根据一个结点计算其父亲节点： 该节点/2就是最近的父亲节点

        //判断是不是自身就是父亲节点
        if(a==b) {
            return a;
        }
        if(a/2==b) {
            return  b;
        }
        if (a==b/2) {
            return a;
        }
        // 是不是兄弟结点
        if(a/2==b/2){
            return a/2;
        }
        // 其中有一个就是父节点
        if(a%b==0 || (a-1)%b==0) {
            return b;
        }
        if(b%a==0 || (b-1)%a==0) {
            return a;
        }
        // 都不是以上情况就需要一步一步往上找（相当于递归）
        return getLCA(a/2,b/2);
    }*/





}
